// #define print(...)
#define sum4(a, d) ( *(a) + *((d)-2) + *((d)-1) + *(d) )
#define sump(a,b,c,d) ( *(a) + *(b) + *(c) + *(d) )
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    if(nums.size() < 4) return {};
    sort(nums.begin(), nums.end());
    print("ordered=", nums, "\n")
    if(sum4(nums.end()-4, nums.end()-1) < target) return {};
    
    vector<vector<int>> res;
    for(auto a=nums.begin(); a!=nums.end()-3; a++){
        if(a > nums.begin() && *a == *(a-1)) continue;
        if(target < sum4(a, a+3)) break;
        if(target > sum4(a, nums.end()-1)) continue;
        for(auto b=a+1; b!=nums.end()-2; b++){
            if(b > a+1 && *b == *(b-1)) continue;
            if(target < sum4(a,b+2)) break;
            if(target > sump(a,b,nums.end()-2,nums.end()-1)) continue;
            
            auto p1 = b+1, p2 = nums.end()-1;
            while(p1 < p2){
                auto s = sump(a,b,p1,p2);
                if(s == target){
                    res.push_back({*a, *b, *p1, *p2});
                    do{p1++;}while(p1<p2 && *(p1-1)==*p1);
                    do{p2--;}while(p1<p2 && *(p2+1)==*p2);
                }else{ s < target ? p1++ : --p2; }
            }
        }
    }
    return res;
}
};
